package 算法.leetcode.linked.list;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lchenglong
 * @date 2020/12/14
 */
public class IsPalindrome extends LinkListBase{
    @Test
    public void test() {
        int[] arr = new int[]{1,2,2,1};
        ListNode head = createTestData(arr);
        System.out.println(isPalindrome2(head));
    }
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList();
        for (;head!=null;head=head.next) {
            list.add(head.val);
        }
        int length = list.size() %2==0?list.size()/2:list.size()/2 +1;
        for (int i=0;i<length;i++) {
            if (!list.get(i).equals(list.get(list.size()-i-1)) ) {
                return false;
            }
        }
        return true;
    }

    public boolean isPalindrome2(ListNode head) {
        ListNode fast = head,slow = head;
        while (fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }

        // 反转链表
        ListNode mid = null;
        ListNode node;
        for (;slow!=null;) {
            // 摘除头结点
            node = slow;
            slow = slow.next;

            // 头插的新链表
            node.next = mid;
            mid = node;
        }
        boolean res = true;
        for (;head!=null  && mid!=null;head = head.next,mid = mid.next) {
            if (head.val!=mid.val) {
                res = false;
                break;
            }
        }
        return res;

    }
}
